package org.labuladong.动态规划算法.二维DP;

import java.util.Arrays;

/**
 * @Auther: qingle
 * @Date: 2024/10/26-20:21
 * @Description:
 * 给你⼀个整数数组 coins 表示不同⾯额的硬币（硬币个数⽆限），另给⼀个整数 amount 表示总⾦额。请你计算并返回可以凑成总⾦额的硬币组合数，如果任何硬币组合都⽆法凑出总⾦额，返回 0。
 * @version: 1.0
 */
public class LC_518零钱兑换II {

	public int change(int amount, int[] coins) {
		// dp[i] 表示凑成金额 i 时的组合数
		int[] dp = new int[amount + 1];
		// 初始化 dp[0] = 1，因为凑成金额 0 有一种方式，即不使用任何硬币
		dp[0] = 1;

		for (int coin : coins) {
			for (int j = coin; j <= amount; j++) {
				// 如果当前金额 j 可以由硬币 coin 组成，则更新 dp[j]
				dp[j] += dp[j - coin];
			}
		}

		// 返回凑成总金额 amount 的组合数
		return dp[amount];
	}

	public static void main(String[] args) {
		LC_518零钱兑换II solution = new LC_518零钱兑换II();
		int[] coins = {1, 2, 5}; // 示例硬币数组
		int amount = 5; // 示例总金额
		int result = solution.change(amount, coins);
		System.out.println("组合数为: " + result);
	}

}
